package dp.xunfei;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Description
 * @Author Firenut
 * @Date 2023-07-10 15:15
 */
public class GoodString {
    public static int solve2(int n, String s) {
        int[] f = new int[n + 1];
        f[0] = 0;

        int[][] MAXS = new int[26][2];
        for (int i = 0; i < 26; i++) {
            MAXS[i][0] = -1;
            MAXS[i][1] = -1;
        }

        for (int i = 1; i <= n; i++) {
            int[] max = MAXS[s.charAt(i - 1) - 'a'];
            if (max[0] != -1) {
                f[i] = f[max[1]] + 1;
            }
            if (max[0] < f[i - 1]) {
                MAXS[s.charAt(i - 1) - 'a'][0] = f[i - 1];
                MAXS[s.charAt(i - 1) - 'a'][1] = i - 1;
            }
        }

        return f[n];
    }

    public static int solve1(int n, String s) {
        int[] f = new int[n + 1];
        Arrays.fill(f, -1);

        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (s.charAt(j - 1) == s.charAt(i - 1) && f[j - 1] != -1) {
                    f[i] = Math.max(f[i], f[j - 1] + 1);
                }
            }
        }
        return f[n];
    }

    public static void main(String[] args) {
//        int n = 7;
//        String s = "abcbdea";
        int n = 2;
        String s = "aba";
        int result = solve2(n, s);
        System.out.println(result);
    }
}
